home *** CD-ROM | disk | FTP | other *** search
/ GFX Sensations 1 / Graphic Sensations - Volume 1.iso / tools / amiga / 3d_tools / irit40s.lha / Irit / irit / bool-2d.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-12-30  |  14.9 KB  |  508 lines
  1. /*****************************************************************************
  2. *   "Irit" - the 3d (not only polygonal) solid modeller.             *
  3. *                                         *
  4. * Written by:  Gershon Elber                Ver 0.2, Mar. 1990   *
  5. ******************************************************************************
  6. *   Module to handle Boolean operation between two polygons in the XY plane. *
  7. * The Z coords. are totally ignored. Input polygons are assumed to be convex.*
  8. *****************************************************************************/
  9.  
  10. /* #define DEBUG2             If defined, defines some printing routines. */
  11.  
  12. #include <stdio.h>
  13. #include <ctype.h>
  14. #include <math.h>
  15. #include <string.h>
  16. #include <signal.h>
  17. #include "program.h"
  18. #include "allocate.h"
  19. #include "booleanl.h"
  20. #include "booleang.h"
  21. #include "convex.h"
  22. #include "geomat3d.h"
  23. #include "intrnrml.h"
  24. #include "objects.h"
  25. #include "windows.h"
  26.  
  27. #define Z_CROSS_PROD(V1, V2) (V1[0] * V2[1] - V1[1] * V2[0])
  28.  
  29. typedef struct Bool2DInterStruct {  /* Hold info. on two intersetion points. */
  30.     struct Bool2DInterStruct *Pnext;
  31.     IPVertexStruct *Poly1Vrtx, *Poly2Vrtx;  /* Pointer to Pl1/2 inter. vrtx. */
  32.     RealType Param1, Param2;     /* Parametrization along the poly vertices. */
  33.     PointType InterPt;
  34.     VectorType Normal;
  35. } Bool2DInterStruct;
  36.  
  37. static IPPolygonStruct *MergeTwoPolygons(IPPolygonStruct *Pl1,
  38.                      IPPolygonStruct *Pl2);
  39. static IPPolygonStruct *Boolean2DCombine(IPPolygonStruct *Pl1,
  40.                      IPPolygonStruct *Pl2);
  41. static Bool2DInterStruct *Boolean2DComputeInters(IPPolygonStruct *Pl1,
  42.                          IPPolygonStruct *Pl2);
  43. static void SortParam(Bool2DInterStruct **Bool2D, int First);
  44. static IPPolygonStruct *Boolean2DCompute1InOut2(IPPolygonStruct *Pl1,
  45.                             IPPolygonStruct *Pl2,
  46.                             Bool2DInterStruct **Bool2D,
  47.                             int Pl1First, int ComputeOut);
  48. static IPPolygonStruct *Boolean2DReverse(IPPolygonStruct *PlHead);
  49.  
  50. #ifdef DEBUG2
  51. static void PrintVrtxList(IPVertexStruct *V);
  52. #endif /* DEBUG2 */
  53.  
  54. /*****************************************************************************
  55. * Given two polygons assumed to be in the same plane, compute their Boolean  *
  56. * operation BoolOper and return it as a new polygon.                 *
  57. * NULL is returned if an error occur (No intersection or invalid BoolOper).  *
  58. *****************************************************************************/
  59. IPPolygonStruct *Boolean2D(IPPolygonStruct *Pl1, IPPolygonStruct *Pl2,
  60.                                 int BoolOper)
  61. {
  62.     IPPolygonStruct *RetVal;
  63.     Bool2DInterStruct
  64.     *Bool2D = Boolean2DComputeInters(Pl1, Pl2);
  65.  
  66.     if (Bool2D == NULL) {
  67.     IPPolygonStruct *PlOut, *PlIn;
  68.  
  69.     /* Coplanar polygons have no intersection. Test for inclusion. */
  70.     if ((CGPolygonRayInter(Pl1, Pl2 -> PVertex -> Coord, 0) & 0x01) == 1) {
  71.         /* Pl2 is enclosed within Pl1 */
  72.         PlOut = Pl1;
  73.         PlIn = Pl2;
  74.     }
  75.     else if ((CGPolygonRayInter(Pl2,
  76.                     Pl1 -> PVertex -> Coord, 0) & 0x01) == 1) {
  77.         /* Pl1 is enclosed within Pl2 */
  78.         PlOut = Pl2;
  79.         PlIn = Pl1;
  80.     }
  81.     else {
  82.         PlOut = NULL;
  83.         PlIn = NULL;
  84.     }
  85.  
  86.     RetVal = NULL;
  87.     switch (BoolOper) {
  88.         case BOOL_OPER_OR:
  89.             if (PlOut != NULL)
  90.             RetVal = IPAllocPolygon(PlOut -> Count, PlOut -> Tags,
  91.                   CopyVertexList(PlOut -> PVertex), NULL);
  92.         break;
  93.         case BOOL_OPER_AND:
  94.             if (PlIn != NULL)
  95.             RetVal = IPAllocPolygon(PlIn -> Count, PlIn -> Tags,
  96.                   CopyVertexList(PlIn -> PVertex), NULL);
  97.         break;
  98.         case BOOL_OPER_SUB:
  99.         if (PlOut == Pl1) {
  100.             /* Merge the two polygons PlOut as is and PlIn reversed. */
  101.             RetVal = MergeTwoPolygons(
  102.             IPAllocPolygon(PlOut -> Count, PlOut -> Tags,
  103.                        CopyVertexList(PlOut -> PVertex), NULL),
  104.             IPAllocPolygon(PlIn -> Count, PlIn -> Tags,
  105.                        CopyVertexList(PlIn -> PVertex), NULL));
  106.         }
  107.         break;
  108.         default:
  109.         IritFatalError("Unsupported 2D Boolean operation");
  110.         RetVal = NULL;
  111.         break;
  112.     }
  113.  
  114.     return RetVal;
  115.     }
  116.  
  117.     switch (BoolOper) {
  118.     case BOOL_OPER_OR:
  119.         RetVal = Boolean2DCombine(Boolean2DCompute1InOut2(Pl1, Pl2, &Bool2D,
  120.                                   TRUE, TRUE),
  121.                       Boolean2DCompute1InOut2(Pl2, Pl1, &Bool2D,
  122.                                    FALSE, TRUE));
  123.         break;
  124.     case BOOL_OPER_AND:
  125.         RetVal = Boolean2DCombine(Boolean2DCompute1InOut2(Pl1, Pl2, &Bool2D,
  126.                                   TRUE, FALSE),
  127.                       Boolean2DCompute1InOut2(Pl2, Pl1, &Bool2D,
  128.                                   FALSE, FALSE));
  129.         break;
  130.     case BOOL_OPER_SUB:
  131.         RetVal = Boolean2DCombine(Boolean2DCompute1InOut2(Pl1, Pl2, &Bool2D,
  132.                                   TRUE, TRUE),
  133.                       Boolean2DReverse(
  134.                       Boolean2DCompute1InOut2(Pl2, Pl1, &Bool2D,
  135.                                   FALSE, FALSE)));
  136.         break;
  137.     default:
  138.         IritFatalError("Unsupported 2D Boolean operation");
  139.         RetVal = NULL;
  140.         break;
  141.     }
  142.  
  143.     while (Bool2D) {
  144.     Bool2DInterStruct
  145.         *NextBool2D = Bool2D -> Pnext;
  146.  
  147.     IritFree((VoidPtr) Bool2D);
  148.     Bool2D = NextBool2D;
  149.     }
  150.  
  151.     return RetVal;
  152. }
  153.  
  154. /*****************************************************************************
  155. * Merge the two provided polygons. Pl1 is assumed to fully contain Pl2.      *
  156. * Pl1/2 are assumed to be convex. Pl2 vertex list is reversed and the two    *
  157. * polygon's vertex lists are connected via the maximum X vertices.         *
  158. * This function is destructive and Pl1/2 are modifed in place.             *
  159. *****************************************************************************/
  160. static IPPolygonStruct *MergeTwoPolygons(IPPolygonStruct *Pl1,
  161.                      IPPolygonStruct *Pl2)
  162. {
  163.     RealType MaxX;
  164.     IPVertexStruct *V, *VMaxX1Copy, *VMaxX2Copy,
  165.     *VMaxX1 = NULL,
  166.     *VMaxX2 = NULL;
  167.  
  168.     IritPrsrReverseVrtxList(Pl2);
  169.  
  170.     /* FInd the vertices in both polygons with the maximum X value. */
  171.     V = Pl1 -> PVertex;
  172.     MaxX = -INFINITY;
  173.     do {
  174.     if (V -> Coord[0] > MaxX) {
  175.         VMaxX1 = V;
  176.         MaxX = V -> Coord[0];
  177.     }
  178.     V = V -> Pnext;
  179.     } while (V != NULL && V != Pl1 -> PVertex);
  180.  
  181.     V = Pl2 -> PVertex;
  182.     MaxX = -INFINITY;
  183.     do {
  184.     if (V -> Coord[0] > MaxX) {
  185.         VMaxX2 = V;
  186.         MaxX = V -> Coord[0];
  187.     }
  188.     V = V -> Pnext;
  189.     } while (V != NULL && V != Pl2 -> PVertex);
  190.  
  191.     /* Duplicate this maximum points. */
  192.     VMaxX1Copy = IPAllocVertex(VMaxX1 -> Tags, VMaxX1 -> Count, NULL,
  193.                    VMaxX1 -> Pnext);
  194.     PT_COPY(VMaxX1Copy -> Coord, VMaxX1 -> Coord);
  195.     PT_COPY(VMaxX1Copy -> Normal, VMaxX1 -> Normal);
  196.  
  197.     VMaxX2Copy = IPAllocVertex(VMaxX2 -> Tags, VMaxX2 -> Count, NULL,
  198.                    VMaxX2 -> Pnext);
  199.     PT_COPY(VMaxX2Copy -> Coord, VMaxX2 -> Coord);
  200.     PT_COPY(VMaxX2Copy -> Normal, VMaxX2 -> Normal);
  201.  
  202.     /* And exchange pointers. */
  203.     VMaxX1 -> Pnext = VMaxX2Copy;
  204.     IP_SET_INTERNAL_VRTX(VMaxX1);
  205.     VMaxX2 -> Pnext = VMaxX1Copy;
  206.     IP_SET_INTERNAL_VRTX(VMaxX2);
  207.  
  208.     Pl2 -> PVertex = NULL;
  209.     IPFreePolygonList(Pl2);
  210.  
  211.     IP_RST_CONVEX_POLY(Pl1);
  212.  
  213.     return Pl1;
  214. }
  215.  
  216. /*****************************************************************************
  217. * Connects the two provided lists of polylines into a closed polygon.         *
  218. * Pl1/2 are being used by this routine and being destroyed.             *
  219. *****************************************************************************/
  220. static IPPolygonStruct *Boolean2DCombine(IPPolygonStruct *Pl1,
  221.                      IPPolygonStruct *Pl2)
  222. {
  223.     IPVertexStruct *VTail;
  224.     IPPolygonStruct *Pl, *PlLast,
  225.     *PlOut = NULL;
  226.  
  227.     /* Chain the two lists into one: */
  228.     for (Pl = Pl1; Pl -> Pnext != NULL; Pl = Pl -> Pnext);
  229.     Pl -> Pnext = Pl2;
  230.     for (VTail = Pl1 -> PVertex; VTail -> Pnext != NULL; VTail = VTail -> Pnext);
  231.  
  232.     while (Pl1 != NULL)
  233.     {
  234.     for (PlLast = Pl1, Pl = Pl1 -> Pnext;
  235.          Pl != NULL && !PT_APX_EQ(Pl -> PVertex -> Coord, VTail -> Coord);
  236.          PlLast = Pl, Pl = Pl -> Pnext);
  237.     if (Pl == NULL) {
  238.         IritFatalError("Boolean2D: Failed to match polylines.");
  239.         return NULL;
  240.     }
  241.  
  242.     VTail -> Pnext = Pl -> PVertex -> Pnext;
  243.  
  244.     /* Free the merged polyline (with its first vertex). */
  245.     PlLast -> Pnext = Pl -> Pnext;
  246.     Pl -> PVertex -> Pnext = NULL;
  247.     IPFreePolygon(Pl);
  248.  
  249.     /* Update the Tail pointer. */
  250.     for ( ; VTail -> Pnext != NULL; VTail = VTail -> Pnext);
  251.  
  252.     if (PT_APX_EQ(VTail -> Coord, Pl1 -> PVertex -> Coord)) {
  253.         /* We closed a loop here. Add to output list. */
  254.         Pl = Pl1 -> Pnext;
  255.         Pl1 -> Pnext = PlOut;
  256.         PlOut = Pl1;
  257.  
  258.         /* Close the loop and remove the duplicate vertex. */
  259.         VTail -> Pnext = Pl1 -> PVertex -> Pnext;
  260.         IPFreeVertex(Pl1 -> PVertex);
  261.         Pl1 -> PVertex = VTail;
  262.  
  263.         /* Continue with next polygon. */
  264.         if ((Pl1 = Pl) != NULL) {
  265.         for (VTail = Pl1 -> PVertex;
  266.              VTail -> Pnext != NULL;
  267.              VTail = VTail -> Pnext);
  268.         }
  269.     }
  270.     }
  271.  
  272.     return PlOut;
  273. }
  274.  
  275. /*****************************************************************************
  276. * Given two polygons, Detect all edges in Pl1 that intersect with edges in   *
  277. * Pl2. Returned is the information about all intersections as a Bool2DInter  *
  278. * structure list.                                 *
  279. *****************************************************************************/
  280. static Bool2DInterStruct *Boolean2DComputeInters(IPPolygonStruct *Poly1,
  281.                          IPPolygonStruct *Poly2)
  282. {
  283.     Bool2DInterStruct *Bool2D,
  284.     *Bool2DHead = NULL;
  285.     RealType Pl1Param, Pl2Param;
  286.     RealType *Pl1, *Pl2, t1, t2;
  287.     PointType Pt1, Pt2;
  288.     VectorType Vl1, Vl2;
  289.     IPVertexStruct *V1, *V2,
  290.     *V1Head = Poly1 -> PVertex,
  291.     *V2Head = Poly2 -> PVertex;
  292.  
  293.     V1 = V1Head;
  294.     Pl1Param = 0.0;
  295.     do {
  296.     Pl1 = V1 -> Coord;
  297.     PT_SUB(Vl1, V1 -> Pnext -> Coord, Pl1);
  298.  
  299.     V2 = V2Head;
  300.         Pl2Param = 0.0;
  301.     do {
  302.         Pl2 = V2 -> Coord;
  303.         PT_SUB(Vl2, V2 -> Pnext -> Coord, Pl2);
  304.  
  305.         if (CG2PointsFromLineLine(Pl1, Vl1, Pl2, Vl2, Pt1, &t1, Pt2, &t2) &&
  306.         t1 > 0.0 && t1 <= 1.0 && t2 > 0.0 && t2 <= 1.0) {
  307.         /* We detected an intersection here. */
  308.         Bool2D = (Bool2DInterStruct *)
  309.                    IritMalloc(sizeof(Bool2DInterStruct));
  310.         PT_COPY(Bool2D -> InterPt, Pt1);
  311.         InterpNrmlBetweenTwo2(Pt1, Bool2D -> Normal, V1, V2);
  312.  
  313.         Bool2D -> Poly1Vrtx = V1;
  314.         Bool2D -> Param1 = Pl1Param + t1;
  315.         Bool2D -> Poly2Vrtx = V2;
  316.         Bool2D -> Param2 = Pl2Param + t2;
  317.  
  318.         Bool2D -> Pnext = Bool2DHead;
  319.         Bool2DHead = Bool2D;
  320.         }
  321.  
  322.         Pl2Param += 1.0;
  323.         V2 = V2 -> Pnext;
  324.     }
  325.     while (V2 != NULL && V2 != V2Head);
  326.  
  327.     Pl1Param += 1.0;
  328.     V1 = V1 -> Pnext;
  329.     }
  330.     while (V1 != NULL && V1 != V1Head);
  331.  
  332.     if (Bool2DHead != NULL && Bool2DHead -> Pnext == NULL) {
  333.     /* If only one intersection - ignore it (point intersection). */
  334.     IritFree((VoidPtr) Bool2DHead);
  335.     Bool2DHead = NULL;
  336.     }
  337.     
  338.     return Bool2DHead;
  339. }
  340.  
  341. /*****************************************************************************
  342. * Sort the provided list with according to Param1 (First) or Param2 (!First) *
  343. *****************************************************************************/
  344. static void SortParam(Bool2DInterStruct **Bool2D, int First)
  345. {
  346.     Bool2DInterStruct
  347.     *Bool2DSorted = NULL;
  348.  
  349.     while (*Bool2D != NULL) {
  350.     Bool2DInterStruct *BTmp,
  351.         *B = *Bool2D;
  352.  
  353.     *Bool2D = (*Bool2D) -> Pnext;
  354.     B -> Pnext = NULL;
  355.  
  356.     if (Bool2DSorted) {
  357.         if ((First && Bool2DSorted -> Param1 > B -> Param1) ||
  358.         (!First && Bool2DSorted -> Param2 > B -> Param2)) {
  359.         /* Put it as first in list. */
  360.         B -> Pnext = Bool2DSorted;
  361.         Bool2DSorted = B;
  362.         }
  363.         else {
  364.         for (BTmp = Bool2DSorted;
  365.              BTmp -> Pnext != NULL;
  366.              BTmp = BTmp -> Pnext)
  367.             if ((First && BTmp -> Pnext -> Param1 > B -> Param1) ||
  368.             (!First && BTmp -> Pnext -> Param2 > B -> Param2))
  369.             break;
  370.         B -> Pnext = BTmp -> Pnext;
  371.         BTmp -> Pnext = B;
  372.         }
  373.     }
  374.     else
  375.         Bool2DSorted = B;
  376.     }
  377.  
  378.     *Bool2D = Bool2DSorted;
  379. }
  380.  
  381. /*****************************************************************************
  382. * Given two polygons, Computes the region(s) of Pl1 out of Pl2.             *
  383. *****************************************************************************/
  384. static IPPolygonStruct *Boolean2DCompute1InOut2(IPPolygonStruct *Pl1,
  385.                             IPPolygonStruct *Pl2,
  386.                             Bool2DInterStruct **Bool2D,
  387.                             int Pl1First, int ComputeOut)
  388. {
  389.     VectorType V1, V2;
  390.     IPVertexStruct *V, *VTail, *VTmp, *VTmp2,
  391.     *VHead = Pl1 -> PVertex;
  392.     IPPolygonStruct *Pl,
  393.     *PlOut = NULL;
  394.     Bool2DInterStruct *B, *NextB;
  395.  
  396.     SortParam(Bool2D, Pl1First);
  397.  
  398.     for (B = *Bool2D; B != NULL; B = B -> Pnext) {
  399.     NextB = B -> Pnext ? B -> Pnext : *Bool2D;
  400.  
  401.     VTmp = Pl1First ? B -> Poly1Vrtx : B -> Poly2Vrtx;
  402.     if (PT_APX_EQ(B -> InterPt, VTmp -> Coord))
  403.         PT_SUB(V1, VTmp -> Pnext -> Coord, B -> InterPt)
  404.     else
  405.         PT_SUB(V1, B -> InterPt, VTmp -> Coord)
  406.  
  407.     VTmp = Pl1First ? B -> Poly2Vrtx : B -> Poly1Vrtx;
  408.     if (PT_APX_EQ(B -> InterPt, VTmp -> Coord))
  409.         PT_SUB(V2, VTmp -> Pnext -> Coord, B -> InterPt)
  410.     else
  411.         PT_SUB(V2, B -> InterPt, VTmp -> Coord)
  412.  
  413.         if ((Z_CROSS_PROD(V1, V2) < 0.0) ^ (ComputeOut != FALSE)) {
  414.         VTmp = Pl1First ? B -> Poly1Vrtx : B -> Poly2Vrtx;
  415.         VHead = VTail = IPAllocVertex(VTmp -> Count, VTmp -> Tags,
  416.                       NULL, NULL);
  417.         PT_COPY(VHead -> Coord, B -> InterPt);
  418.         PT_COPY(VHead -> Normal, B -> Normal);
  419.  
  420.         VTmp2 = Pl1First ? NextB -> Poly1Vrtx : NextB -> Poly2Vrtx;
  421.         if (VTmp != VTmp2)
  422.         for (V = VTmp -> Pnext;
  423.              V != VTmp2 -> Pnext;
  424.              V = V -> Pnext) {
  425.             VTail -> Pnext =
  426.             IPAllocVertex(V -> Count, V -> Tags, NULL, NULL);
  427.             VTail = VTail -> Pnext;
  428.             PT_COPY(VTail -> Coord, V -> Coord);
  429.         PT_COPY(VTail -> Normal, V -> Normal);
  430.         }
  431.  
  432.         VTail -> Pnext = IPAllocVertex(VTmp2 -> Count, VTmp2 -> Tags,
  433.                        NULL, NULL);
  434.         VTail = VTail -> Pnext;
  435.         PT_COPY(VTail -> Coord, NextB -> InterPt);
  436.         PT_COPY(VTail -> Normal, NextB -> Normal);
  437.  
  438.         Pl = IPAllocPolygon(0, 0, VHead, NULL);
  439.         PLANE_COPY(Pl -> Plane, Pl1 -> Plane);
  440.         Pl -> Pnext = PlOut;
  441.         PlOut = Pl;
  442.     }
  443.     }
  444.  
  445.     if (PlOut == NULL)
  446.     IritFatalError("Bool2D: Failed to compute in/out.");
  447.     return PlOut;
  448. }
  449.  
  450. /*****************************************************************************
  451. * Given a polyline (= list of IPVertexStruct), computes the reverse of the     *
  452. * list, in place. Returns pointer to reversed list.                 *
  453. *****************************************************************************/
  454. static IPPolygonStruct *Boolean2DReverse(IPPolygonStruct *PlHead)
  455. {
  456.     IPPolygonStruct *Pl;
  457.  
  458.     for (Pl = PlHead; Pl != NULL; Pl = Pl -> Pnext) {
  459.     IPVertexStruct *VNextNext, *V, *VNext;
  460.  
  461.     V = Pl -> PVertex;
  462.     VNext = V -> Pnext;
  463.  
  464.     while (VNext != NULL) {
  465.         VNextNext = VNext -> Pnext;
  466.         VNext -> Pnext = V;                 /* Reverse the pointer! */
  467.  
  468.         V = VNext;               /* Advance all 3 pointers by one. */
  469.         VNext = VNextNext;
  470.     }
  471.     Pl -> PVertex -> Pnext = NULL;
  472.     Pl -> PVertex = V;
  473.  
  474.     /* Move the Tags. */
  475.     while (V -> Pnext != NULL) {
  476.         V -> Tags = V -> Pnext -> Tags;
  477.         V -> Count = V -> Pnext -> Count;
  478.  
  479.         V = V -> Pnext;
  480.     }
  481.     }
  482.     return PlHead;
  483. }
  484.  
  485. #ifdef DEBUG2
  486.  
  487. /*****************************************************************************
  488. *   Print the content of the given polygon, to standard output.             *
  489. *****************************************************************************/
  490. static void PrintVrtxList(IPVertexStruct *V)
  491. {
  492.     IPVertexStruct
  493.     *VHead = V;
  494.  
  495.     do {
  496.     printf("    %12lf %12lf %12lf",
  497.            V -> Coord[0], V -> Coord[1], V -> Coord[2]);
  498.     if (IS_INTERNAL_EDGE(V))
  499.         printf(" (Internal)\n");
  500.     else
  501.         printf("\n");
  502.     V = V -> Pnext;
  503.     }
  504.     while (V!= NULL && V != VHead);
  505. }
  506.  
  507. #endif /* DEBUG2 */
  508.